const { ListToNode, NodeToList, ListNode, timeL } = require("../utils.js");
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  p = p.replace(/\*+/g, "*").replace(/\?/g, ".");
  // 字符串翻转
  const strR = (str) => {
    return str.split("").reverse().join("");
  };
  const arrSlice = (arr, i, item) => {
    let s1 = arr.slice(0, i);
    let s2 = arr.slice(i);
    s1.push("");
    s2.unshift("");
    s1 = s1.join(item);
    s2 = s2.join(item);
    return [s1, s2];
  };
  const fun4 = (s, p, list) => {
    if (list.length > 5) {
      list = list.sort((a, b) => a[1] * a[2] - b[1] * b[2]);
      const item = list[0][0];
      let sL = s.split(item);
      let pL = p.split(item);
      for (let i = 1; i < sL.length; i++) {
        for (let y = 1; y < pL.length; y++) {
          const [s1, s2] = arrSlice(sL, i, item);
          const [p1, p2] = arrSlice(pL, y, item);
          if (fun1(s1, p1, fun2) && fun1(s2, p2, fun2)) return true;
        }
      }
      return false;
    } else {
      let reg = new RegExp(`^${p.replace(/\*/g, "(?:.*?)")}$`);
      return reg.test(s);
    }
  };

  // 简易匹配各个字符是否存在
  const fun3 = (s, p) => {
    // 根据* 分割数组  每项匹配 字符串 查看是否存在
    let obj = {};
    let list = p.split(/\*/).filter((item) => {
      return !!item;
    });
    for (let i = 0; i < list.length; i++) {
      obj[list[i]] = obj[list[i]] || 0;
      obj[list[i]] += 1;
      const reg = new RegExp(list[i], "g");
      let num = s.match(reg)?.length;
      if (!num) return false;
      list[i] = [list[i], num];
    }
    list = list.map((item) => {
      return [...item, obj[item[0]]];
    });
    return fun4(s, p, list);
  };
  // 简易匹配准确字符，删除对应字符
  const fun2 = (s, p) => {
    while (p[0]) {
      if (p[0] === "*") break;
      if (p[0] === s[0] || (p[0] === "." && s[0])) {
        s = s.substring(1);
        p = p.substring(1);
      } else return false;
    }
    s = strR(s);
    p = strR(p);
    while (p[0]) {
      if (p[0] === "*") break;
      if (p[0] === s[0] || p[0] === ".") {
        s = s.substring(1);
        p = p.substring(1);
      } else return false;
    }
    s = strR(s);
    p = strR(p);
    return fun1(s, p, fun3);
  };
  // 只过滤 空
  const fun1 = (s, p, fun) => {
    if (s && !p) return false;
    if (!s && !p) return true;
    if (!s && p) return p === "*";
    return fun(s, p);
  };
  return fun1(s, p, fun2);
};
let s =
    "aabbbbaababbabababaabbbbabbabbaabbbabbbabaabbaaaababababbababbabbbbabaaabaaabaabbaaaabbbbabaaabbbbbabbbaabbbbbabaabababaaabaaababaababbaaabaabbabaababbabababaaababbabbabaabbbbabbbbabaabbaababaaabababbab",
  p =
    "a*b*a*b*aaaa*abaaa**b*a***b*a*bb****ba*ba*b******a********a**baba*ab***a***bbba*b**a*b*ba*a*aaaa*ab**";
// let s =
//     "aaaabaabaabbbabaabaabbbbaabaaabaaabbabbbaaabbbbbbabababbaabbabbbbaababaaabbbababbbaabbbaabbaaabbbaabbbbbaaaabaaabaabbabbbaabababbaabbbabababbaabaaababbbbbabaababbbabbabaaaaaababbbbaabbbbaaababbbbaabbbbb",
//   p =
//     "**a*b*b**b*b****bb******b***babaab*ba*a*aaa***baa****b***bbbb*bbaa*a***a*a*****a*b*a*a**ba***aa*a**a*";
timeL(isMatch, [s, p]);
